package j2025.j01;

/**
 * @Author 猫大仙
 */
public class j0120 {
    /**
     * 152. 乘积最大子数组
     * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
     * 子数组
     * （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     *
     * 测试用例的答案是一个 32-位 整数。
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        double[] f = new double[n + 1];
        double[] g = new double[n + 1];
        f[0] = g[0] = 1.0;
        double ret = Long.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            //nums[i-1]可能为正,也可能为负
            double x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(f[i], ret);
        }
        return (int) ret;
    }

    /**
     * 416. 分割等和子集
     * 给你一个 只包含正整数 的 非空 数组 nums 。
     * 请你判断是否可以将这个数组分割成两个子集，
     * 使得两个子集的元素和相等。
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int half = sum/2;
        boolean[] dp = new boolean[half+1];
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = half; j >=nums[i-1]; j--) {
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[half];
    }
}
